//给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
//
//
//
// 示例 :
//给定二叉树
//
//           1
//         / \
//        2   3
//       / \
//      4   5
//
//
// 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
//
//
//
// 注意：两结点之间的路径长度是以它们之间边的数目表示。
// Related Topics 树 深度优先搜索 二叉树 👍 1111 👎 0

package leetcode.editor.cn;

class 二叉树的直径 {
    public static void main(String[] args) {
        Solution solution = new 二叉树的直径().new Solution();

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        class Info {
            private int maxDistance;
            private int height;

            public Info(int maxDistance, int height) {
                this.maxDistance = maxDistance;
                this.height = height;
            }
        }

        public int diameterOfBinaryTree(TreeNode root) {
            return process(root).maxDistance;
        }

        private Info process(TreeNode root) {
            if (root == null) {
                return new Info(0, 0);
            }
            Info leftInfo = process(root.left);
            Info rightInfo = process(root.right);
            int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), leftInfo.height + rightInfo.height);
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            return new Info(maxDistance, height);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
